// 752. 打开转盘锁

function openLock(deadends: string[], target: string): number {
    const visited = new Set<string>(deadends)
    const que = []
    if(visited.has('0000')) return -1
    que.push('0000')
    let level = 0
    while(que.length){
        let len = que.length
        for(let i=0;i<len;i++){
            const tmp = que.shift()!
            if(tmp==target) return level
            const next = getNext(tmp)
            for(let it of next){
                if(!visited.has(it)){
                    que.push(it)
                    visited.add(it)
                }
            }
        }
        level++
    }
    return -1
};

function getNext(start:string):string[]{
    const next:string[] = []
    const base = '0'.charCodeAt(0)
    for(let i=0;i<4;i++){
        const c = start.charCodeAt(start.length-i-1)
        let t1 = start.substring(0,start.length-i-1)+`${(c-base+10-1)%10}`
        let t2 = start.substring(0,start.length-i-1)+`${(c-base+10+1)%10}`
        t1+= start.substring(start.length-i)
        t2+= start.substring(start.length-i)
        next.push(t1)
        next.push(t2)
    }
    return next
}

console.log(openLock(["0201","0101","0102","1212","2002"],  "0202"))